Ví dụ thuật toán

Một trong những thuật toán đơn giản nhất là tìm số lớn nhất trong danh sách các số có thứ tự ngẫu nhiên. Tìm lời giải yêu cầu nhìn vào mọi số trong danh sách. Từ đó dẫn đến một thuật toán đơn giản, có thể được nêu trong phần mô tả cấp cao bằng văn xuôi tiếng Anh, như:

Mô tả cấp cao:

1. Nếu không có số nào trong tập hợp thì không có số cao nhất.
2. Giả sử số đầu tiên trong tập hợp là số lớn nhất trong tập hợp.
3. Với mỗi số còn lại trong tập hợp: nếu số này lớn hơn số lớn nhất hiện tại thì coi số này là số lớn nhất trong tập hợp.
4. Khi không còn số nào trong tập hợp để lặp lại, hãy coi số lớn nhất hiện tại là số lớn nhất của tập hợp.

Bán mô tả chính thức: Được viết bằng văn xuôi nhưng gần với ngôn ngữ cấp cao của chương trình máy tính hơn nhiều, sau đây là cách mã hóa chính thức hơn của thuật toán bằng mã giả hoặc mã pidgin:Bản mẫu:Algorithm-begin

 Input: A list of numbers L. Output: The largest number in the list L.

 if L.size = 0 return null largest ← L[0] for each item in L, doif item > largest, then largest ← item return largest

Bản mẫu:Algorithm-end

Thuật toán Euclid

Thuật toán của Euclid để tính ước số chung lớn nhất (ƯCLN) cho hai số xuất hiện dưới dạng Mệnh đề II trong Quyển VII ("Lý thuyết số cơ bản") của tác phẩm Cơ sở của ông.[50] Do đó, Euclid đặt ra vấn đề: "Cho hai số không nguyên tố với nhau, hãy tìm số đo chung lớn nhất của chúng". Ông định nghĩa "Một số [là] một vô số bao gồm các đơn vị": một số đếm, một số nguyên dương không bao gồm số không. Để "đo" là đặt một chiều dài ngắn s liên tiếp (q lần) lên trên chiều dài l cho đến khi phần còn lại là r nhỏ hơn chiều dài ngắn s. [51] Nói cách hiện đại, phần dư r = l - q × s, q là thương số, hoặc phần dư r là "môđun", phần nguyên còn lại sau phép chia.[52]

Để phương pháp Euclid thành công, độ dài bắt đầu phải thỏa mãn hai yêu cầu: (i) độ dài không được bằng 0, VÀ (ii) phép trừ phải “hợp lệ”; tức là, một phép thử phải đảm bảo rằng số nhỏ hơn trong hai số bị trừ đi số lớn hơn (hoặc hai số có thể bằng nhau để phép trừ của chúng cho kết quả bằng không).

Chứng minh ban đầu của Euclid bổ sung thêm một yêu cầu thứ ba: hai độ dài không được nguyên tố với nhau. Euclid đã quy định điều này để ông có thể xây dựng một bằng chứng rút gọn là vô lý rằng số đo chung của hai số trên thực tế là lớn nhất.[53] Trong khi thuật toán của Nicomachus cũng giống như thuật toán của Euclid, khi các số nguyên tố với nhau, nó mang lại số "1" cho số đo chung của chúng. Vì vậy, chính xác mà nói, sau đây thực sự là thuật toán của Nicomachus.

 1599 = 650×2 + 299 650 = 299×2 + 52 299 = 52×5 + 39 52 = 39×1 + 13 39 = 13×3 + 0

Ngôn ngữ máy tính cho thuật toán Euclid

Chỉ một số loại lệnh được yêu cầu để thực thi thuật toán Euclid — một số phép thử logic (GOTO có điều kiện), GOTO không điều kiện, phép gán (thay thế) và phép trừ.

• Vị trí được ký hiệu bằng (các) chữ cái viết hoa, ví dụ: S, A, v.v.
• Số lượng (số) khác nhau ở một vị trí được viết bằng (các) chữ cái thường và (thường) được kết hợp với tên của vị trí. Ví dụ, vị trí L ở đầu có thể chứa số l = 3009.

Một chương trình không thanh lịch cho thuật toán Euclid

Thuật toán sau đây được đóng khung như là phiên bản bốn bước của Knuth của Euclid's và Nicomachus, nhưng thay vì sử dụng phép chia để tìm phần dư, nó sử dụng các phép trừ liên tiếp của độ dài s từ độ dài còn lại r cho đến khi r nhỏ hơn s. Mô tả cấp cao, được in đậm, được phỏng theo Knuth 1973: 2–4:

ĐẦU VÀO:

1 [Into two locations L and S put the numbers l and s that represent the two lengths]: INPUT L, S

2 [Initialize R: make the remaining length r equal to the starting/initial/input length l]: R ← L

E0: [Đảm bảo r ≥ s. ]

3 [Ensure the smaller of the two numbers is in S and the larger in R]: IF R > S THEN the contents of L is the larger number so skip over the exchange-steps 4, 5 and 6: GOTO step 6 ELSE swap the contents of R and S.

4 L ← R (this first step is redundant, but is useful for later discussion).

5 R ← S

6 S ← L

E1: [Tìm phần dư]: Cho đến khi độ dài còn lại r trong R nhỏ hơn độ dài ngắn hơn s trong S, lặp đi lặp lại phép trừ số đo s trong S với độ dài còn lại r trong R.

7 IF S > R THEN done measuring so GOTO 10 ELSE measure again,

8 R ← R − S

9 [Remainder-loop]: GOTO 7.

E2: [Phần dư có bằng 0? ]: HOẶC (i) số đo cuối cùng là chính xác, phần còn lại trong R bằng 0 và chương trình có thể tạm dừng, HOẶC (ii) thuật toán phải tiếp tục: số đo cuối cùng để lại phần dư trong R nhỏ hơn số đo trong S.

10 IF R = 0 THEN done so GOTO step 15 ELSE CONTINUE TO step 11,

E3: [Đảo vị trí s và r ]: Điểm mấu chốt của thuật toán Euclid. Sử dụng phần dư r để đo số trước đó nhỏ hơn s; L phục vụ như một kho lưu trữ tạm thời.

11 L ← R

12 R ← S

13 S ← L

14 [Repeat the measuring process]: GOTO 7

ĐẦU RA:

15 [Done. S contains the greatest common divisor]: PRINT S

XONG:

16 HALT, END, STOP.

Một chương trình thanh lịch cho thuật toán Euclid

Phiên bản sau của thuật toán Euclid chỉ yêu cầu sáu lệnh cốt lõi để thực hiện mười ba lệnh được yêu cầu bởi "chương trình chưa thanh lịch"; tệ hơn nữa là "chương trình chưa thanh lịch" yêu cầu nhiều loại hướng dẫn hơn. [làm rõ] Bạn có thể tìm thấy sơ đồ của "Thanh lịch" ở đầu bài viết này. Trong ngôn ngữ BASIC (không có cấu trúc), các bước được đánh số, và lệnh LET [] = [] là lệnh gán được ký hiệu bằng ←.

 5 REM Euclid's algorithm for greatest common divisor 6 PRINT "Type two integers greater than 0" 10 INPUT A,B 20 IF B=0 THEN GOTO 80 30 IF A > B THEN GOTO 60 40 LET B=B-A 50 GOTO 20 60 LET A=A-B 70 GOTO 20 80 PRINT A 90 END

Cách "chương trình thanh lịch" hoạt động: Thay cho "vòng lặp Euclid" bên ngoài, "Elegant" di chuyển qua lại giữa hai "co-vòng lặp", một vòng lặp A> B tính A ← A - B và một vòng lặp B ≤ A tính toán B ← B - A. Điều này hoạt động bởi vì, khi cuối cùng giá trị nhỏ nhất M nhỏ hơn hoặc bằng dải con S (Chênh lệch = Minuend - Subtrahend), minuend có thể trở thành s (chiều dài đo mới) và subtrahend có thể trở thành r mới (độ dài được đo); nói cách khác, "ý nghĩa" của phép trừ đảo ngược.Phiên bản sau có thể được sử dụng với các ngôn ngữ hướng đối tượng:

// Euclid's algorithm for greatest common divisorint euclidAlgorithm (int A, int B){ A=Math.abs(A); B=Math.abs(B); while (B!=0){   if (A>B) A=A-B;   else B=B-A; } return A;}

Kiểm tra các thuật toán Euclid

Một thuật toán có làm được những gì mà tác giả của nó muốn nó làm không? Một số trường hợp thử nghiệm thường cung cấp một số tin cậy về chức năng cốt lõi. Nhưng các thử nghiệm là không đủ. Đối với các trường hợp thử nghiệm, một nguồn [54] sử dụng 3009 và 884. Knuth đề xuất 40902, 24140. Một trường hợp thú vị khác là hai số nguyên tố cùng nhau 14157 và 5950.

Nhưng "trường hợp ngoại lệ" [55] phải được xác định và thử nghiệm. Liệu "Inelegant" có thực hiện đúng khi R> S, S> R, R = S không? Cũng vậy cho chương trình "Thanh lịch": B> A, A> B, A = B? (Có cho tất cả). Điều gì xảy ra khi một số bằng 0, cả hai số đều bằng không? ("Chưa thanh lịch" rơi vào vòng lặp vĩnh viễn trong các trường hợp trên; "Thanh lịch" rơi vào vòng lặp vĩnh viễn khi A = 0.) Điều gì xảy ra nếu người dùng nhập số âm ? Số phân số? Nếu các số đầu vào, tức là miền của hàm được tính toán bởi thuật toán / chương trình, chỉ bao gồm các số nguyên dương bao gồm cả số 0, thì các lỗi ở số 0 chỉ ra rằng thuật toán (và chương trình khởi tạo nó) là một hàm riêng phần chứ không phải một hàm tổng. Một thất bại đáng chú ý do các ngoại lệ kiểu như vậy là sự cố tên lửa Ariane 5 Flight 501 (ngày 4 tháng 6 năm 1996).

Chứng minh tính đúng đắn của chương trình bằng cách sử dụng quy nạp toán học: Knuth chứng minh việc áp dụng quy nạp toán học cho phiên bản "mở rộng" của thuật toán Euclid và ông đề xuất "một phương pháp chung áp dụng để chứng minh tính hợp lệ của bất kỳ thuật toán nào".[56] Tausworthe đề xuất rằng thước đo độ phức tạp của một chương trình là độ dài của bằng chứng tính đúng đắn của nó.[57]

Đo lường và cải thiện các thuật toán Euclid

Thanh lịch (nhỏ gọn) so với tốt (tốc độ): Chỉ với sáu lệnh cốt lõi, "Thanh lịch" là chiến thắng rõ ràng, so với "Không thanh lịch" với 13 lệnh. Tuy nhiên, "Không thanh lịch" nhanh hơn (nó đến HALT trong ít bước hơn). Phân tích thuật toán [58] chỉ ra lý do tại sao lại như vậy: "Thanh lịch" thực hiện hai phép thử điều kiện trong mỗi vòng trừ, trong khi "Không thanh lịch" chỉ thực hiện một phép thử. Vì thuật toán (thường) yêu cầu nhiều lần lặp lại, nên trung bình sẽ lãng phí nhiều thời gian để thực hiện "B = 0?" kiểm tra chỉ cần thiết sau khi phần còn lại được tính toán.

Các thuật toán có thể được cải thiện không?: Một khi lập trình viên đánh giá một chương trình "phù hợp" và "hiệu quả" - nghĩa là nó tính toán chức năng mà tác giả của nó dự định - thì câu hỏi sẽ trở thành, liệu nó có thể được cải thiện không?

Có thể cải thiện độ nhỏ gọn của "Không thanh lịch" bằng cách loại bỏ năm bước. Nhưng Chaitin đã chứng minh rằng việc nén một thuật toán không thể được tự động hóa bằng một thuật toán tổng quát;[59] đúng hơn, nó chỉ có thể được thực hiện theo kinh nghiệm; tức là, bằng cách tìm kiếm đầy đủ, thử và sai, thông minh, sáng suốt, áp dụng suy luận quy nạp, v.v. Quan sát các bước 4, 5 và 6 được lặp lại trong các bước 11, 12 và 13. So sánh với "Thanh lịch" cung cấp gợi ý rằng các bước này, cùng với các bước 2 và 3, có thể bị loại bỏ. Điều này làm giảm số lượng lệnh cốt lõi từ 13 xuống 8, làm cho nó "thanh lịch" hơn "Thanh lịch", với chín bước.

Tốc độ của "Thanh lịch" có thể được cải thiện bằng cách di chuyển "B = 0?" kiểm tra bên ngoài của hai vòng trừ. Thay đổi này yêu cầu bổ sung ba lệnh (B = 0 ?, A = 0 ?, GOTO). Bây giờ "Thanh lịch" tính toán các số ví dụ nhanh hơn; cho dù điều này luôn đúng đối với bất kỳ A, B và R, S nào cho trước hay không sẽ yêu cầu một phân tích chi tiết.